/*
链表的逆序，使用非递归的方式
1. 尾插法初始化
2. 逆序
*/

#include <iostream>
using namespace std;

//结点定义
struct Node
{
	int data;
	Node* next = NULL;
	Node(int value):data(value){};
	Node(){};
};

//尾插法初始化
Node* RearInsert(Node* head,int arr[],int arrSize){
	Node* rear = head;
	rear->next = NULL;
	for(int i = 0;i < arrSize;i++){
		Node* new_node = new Node(arr[i]);
		new_node->next = rear->next;
		rear->next = new_node;
		rear = rear->next;
	}
	return head;
}

//翻转链表
Node* ReverseLinkList(Node* head){
	Node* p1 = head->next;
	Node* p2 = p1->next;
	Node* p3 = p2->next;
	p1->next = NULL;		//头变尾
	while(p3 != NULL){
		p2->next = p1;
		p1 = p2;
		p2 = p3;
		p3 = p3->next;
	}
	p2->next = p1;
	Node* new_head = new Node;	//生成新头
	new_head->next = p2;
	return new_head;
}

void Print(Node* head){
	Node* cur = head->next;
	while(cur != NULL){
		cout<<cur->data<<"  ";
		cur = cur->next;
	}
	cout<<endl;
}
int main(int argc, char const *argv[])
{
	int arr[5] = {1,2,3,4,5};
	Node* head = new Node;
	head = RearInsert(head,arr,5);
	Print(head);						// 1,2,3,4,5
	Print(ReverseLinkList(head));		// 5,4,3,2,1
	return 0;
}